package pers.qianyu.month_202011.date_20201122;

/**
 * [重要]
 * 98. 验证二叉搜索树
 * https://leetcode-cn.com/problems/validate-binary-search-tree/
 *
 * @author mizzle rain
 * @date 2020-11-22 20:17
 */
public class IsValidBST {
    public boolean isValidBST(TreeNode root) {
        return recur(root, null, null);
    }

    /**
     * 对每个结点的操作：
     * - 判断是左子树还是右子树
     * - 与其父节点进行比较
     * 所以我们要知道两个信息：
     * - 这个节点是左子树还是右子树
     * - 这个节点的父节点的值
     * 通过下面函数传递的两个参数可以巧妙的得知这两个信息
     * - 如果min为 null、max不为null，则说明为左子树，max代表其父节点，需要判断是否比父节点小
     * - 如果min不为 null、max为null，则说明为右子树，min代表其父节点，需要判断是否比父节点大
     */
    private boolean recur(TreeNode root, TreeNode min, TreeNode max) {
        if (root == null) {
            return true;
        }
        boolean res = true;
        if (min != null) {
            res = root.val > min.val;
        }
        if (max != null) {
            res = res && (root.val < max.val);
        }
        return res && recur(root.left, min, root)
                && recur(root.right, root, max);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
